package com.lfx.work;

/**
 * @author 李逢喜
 * create 2021/7/20
 */
public class WorkTwo {

    /**
     * @param values   价值数组
     * @param persions 对应人数
     * @param max      最大人数
     * @return
     */
    public static int maxValue(int[] values, int[] persions, int max) {

        if (values == null || values.length == 0 || persions == null || persions.length == 0) return 0;

        int[][] dp = new int[values.length + 1][max + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= max; j++) {//j=0最大价值是0，因此j从1开始
                if (j < persions[i-1]) {//人数不够不选择这个金矿，因此赋值等于上一轮的最大价值
                    dp[i][j] = dp[i - 1][j];//索引下标为j的值就是上一轮的最大值
                } else {//人数足够选择当前金矿

                    //获取前一轮，下标为j - persions[i - 1]的最大黄金重量
                    int i1 = dp[i - 1][j - persions[i - 1]];
                    //当前最大价值与上一轮的最大比较，取最大值
                    dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - persions[i - 1]]);
                }

            }
        }


        return dp[values.length][max];

    }

    public static void main(String[] args) {
//        int[] values = {60, 30, 50, 40, 60};
//        int[] persions = {2, 2, 6, 5, 4};
        int[] values = {100, 150, 200, 400, 500};
        int[] persions = {2, 2, 3, 4, 5};
        int max = 10;
        System.out.println(maxValue(values, persions, max));
    }
}
